翻訳と辞書
Words near each other
・ Strontium peroxide
・ Strontium ranelate
・ Strontium ruthenate
・ Strontium sulfate
・ Stronghold Center
・ Stronghold Crusader II
・ Stronghold Kingdoms
・ Stronghold Legends
・ Stronghold of Toughs
・ Stronghold – The Collector's Hit Box
・ Stronghold, California
・ Stronghold, Washington, D.C.
・ Stronghurst Township, Henderson County, Illinois
・ Stronghurst, Illinois
・ Strongloop
Strongly chordal graph
・ Strongly compact cardinal
・ Strongly connected component
・ Strongly correlated material
・ Strongly correlated quantum spin liquid
・ Strongly embedded subgroup
・ Strongly interacting massive particle
・ Strongly measurable functions
・ Strongly minimal theory
・ Strongly monotone
・ Strongly positive bilinear form
・ Strongly regular
・ Strongly regular graph
・ Strongly symmetric matter
・ Strongman


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Strongly chordal graph : ウィキペディア英語版
Strongly chordal graph
In the mathematical area of graph theory, an undirected graph ''G'' is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in ''G'' has an ''odd chord'', i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.〔, Definition 3.4.1, p. 43.〕
==Characterizations==
Strongly chordal graphs have a forbidden subgraph characterization as the graphs that do not contain an induced cycle of length greater than three or an ''n''-sun (''n'' ≥ 3) as an induced subgraph.〔; ; , Theorem 7.2.1, p. 112.〕 An ''n''-sun is a chordal graph with 2''n'' vertices, partitioned into two subsets ''U'' =  and ''W'' = , such that each vertex ''wi'' in ''W'' has exactly two neighbors, ''u''''i'' and ''u''(''i'' + 1) mod ''n''. An ''n''-sun cannot be strongly chordal, because the cycle ''u''1''w''1''u''2''w''2... has no odd chord.
Strongly chordal graphs may also be characterized as the graphs having a strong perfect elimination ordering, an ordering of the vertices such that the neighbors of any vertex that come later in the ordering form a clique and such that, for each ''i'' < ''j'' < ''k'' < ''l'', if the ''i''th vertex in the ordering is adjacent to the ''k''th and the ''l''th vertices, and the ''j''th and ''k''th vertices are adjacent, then the ''j''th and ''l''th vertices must also be adjacent.〔; , Theorem 5.5.1, p. 77.〕
A graph is strongly chordal if and only if every one of its induced subgraphs has a simple vertex, a vertex whose neighbors have neighborhoods that are linearly ordered by inclusion.〔; , Theorem 5.5.2, p. 78.〕 Also, a graph is strongly chordal if and only if it is chordal and every cycle of length five or more has a 2-chord triangle, a triangle formed by two chords and an edge of the cycle.〔.〕
A graph is strongly chordal if and only if every one of its induced subgraphs is dually chordal 〔, Corollary 3, p. 444.〕
Strongly chordal graphs may also be characterized in terms of the number of complete subgraphs each edge participates in.〔.〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Strongly chordal graph」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.